/**
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2
解释: [1,1] 与 [1,1] 为两种不同的情况。
 */
function subarraySum(nums, k) {
  let count = 0, sum = 0
  const map = {}
  map[0] = 1
  for(let i = 0; i < nums.length; i++) {
    sum += nums[i]
    if(map[sum - k]) count += map[sum - k]
    map[sum] = (map[sum] || 0) + 1
  }
  return count
}
console.log(subarraySum([9,0,0,3], 3))
/**
 * 思路：前缀和 + 哈希表
 * 
 * 核心思想：
 * - sum 记录当前前缀和（从索引0到i的所有元素的和）
 * - map 记录之前出现过的前缀和及其出现次数
 * - 如果存在前缀和 prevSum = sum - k，那么 sum - prevSum = k
 *   即：从 prevSum 对应的位置到当前位置的子数组和为 k
 * 
 * 为什么检查 map[sum - k] 而不是 map[k]？
 * 
 * 关键理解：我们要找的是"子数组的和"，不是"前缀和等于k"
 * - 子数组的和 = 当前前缀和 - 之前某个前缀和
 * - 即：sum - prevSum = k，所以 prevSum = sum - k
 * 也就是prevSum存在，子数组也存在
 * 如果直接判断 map[k]：
 * - 只能找到"之前某个位置的前缀和等于k"的情况
 * - 但我们需要的是"当前前缀和减去之前某个前缀和等于k
 */